﻿#include "SudokuSolver.h"
#include "SudokuPrinter.h"
#include "SudokuChecker.h"
#include "SudokuMaker.h"
#include "SudokuReader.h"
#include <vector>
using namespace std;


namespace SudokuSolver
{
	Sudoku problem_sudoku;
	Sudoku rule[3];
	Sudoku covered;//covered用于记录初始数独问题，便于回溯


	inline int findGridIndex(int row_idx, int col_idx)
	{
		//grid计数是0~8
		return ((row_idx - 1) / 3 * 3 + (col_idx - 1) / 3);
	}

	inline int findNextValue(int row_idx, int col_idx, int start)
	{
		int index = findGridIndex(row_idx, col_idx);
		for (int i = start; i < 10; i++)
		{
			if (rule[0][row_idx][i]) continue;
			if (rule[1][col_idx][i]) continue;
			if (rule[2][index][i]) continue;
			return i;
		}
		return 0;
	}

	inline void changeRule(int row_idx, int col_idx, int is_exist)
	{
		int index = findGridIndex(row_idx, col_idx);
		int value = problem_sudoku[row_idx][col_idx];
		rule[0][row_idx][value] = is_exist;//用于指示第row_idx行的value已经存在
		rule[1][col_idx][value] = is_exist;//用于指示第col_idx列的value已经存在
		rule[2][index][value] = is_exist;//用于指示第index个grid中的value已经存在
	}


	bool solveSudoku(int row_idx, int col_idx)
	{
		if (col_idx == 10)
		{
			row_idx++;
			col_idx = 1;
		}
		//找到需要填空的位置
		while (row_idx < 10 && covered[row_idx][col_idx])
		{
			col_idx++;
			if (col_idx == 10)
			{
				row_idx++;
				col_idx = 1;
			}
		}
		if (row_idx > 9)
		{
			return true;
		}
		//findNextValue就是找到可以在此位置填充的值
		while (problem_sudoku[row_idx][col_idx] = findNextValue(row_idx, col_idx, problem_sudoku[row_idx][col_idx] + 1))
		{
			changeRule(row_idx, col_idx, 1);
			if (solveSudoku(row_idx, col_idx + 1))
				return true;
			changeRule(row_idx, col_idx, 0);
		}
		return false;
	}

	void initSolver()
	{
		for (int k = 0; k < 3; k++)
			for (int i = 0; i < 10; i++)
				ZeroMemory(rule[k][i], sizeof(int) * 10);

		for (int i = 1; i < 10; i++)
		{
			for (int j = 1; j < 10; j++)
			{
				if (problem_sudoku[i][j])
				{
					covered[i][j] = 1;
					changeRule(i, j, 1);
				}
				else
				{
					covered[i][j] = 0;
				}
			}
		}
	}

}
void solveSudokuProblem()
{
	mallocSudoku(SudokuSolver::covered);
	for (int i = 0; i < 3; i++)
		mallocSudoku(SudokuSolver::rule[i]);
	//判断读入文件的换行格式是CRLF还是LF
	judgeCRLF();
	for (int i = 0; i < BUFF_SIZE + 1; i++)
		mallocSudoku(read_buff[i]);
	bool is_end = false;
	while (!is_end)//没有读完就一直读
	{
		int num_in_read_buff = 0;
		readSudoku(is_end, num_in_read_buff);//readSudoku会修改is_end和num_in_read_buff的值
		for (int i = 0; i < num_in_read_buff; i++)
		{
			SudokuSolver::problem_sudoku = read_buff[i];
			//showSudoku(problem_sudoku);
			SudokuSolver::initSolver();//初始化相关变量，便于后续求解
			//showSudoku(covered);
			//showSudoku(rule[0]);
			//showSudoku(rule[1]);
			SudokuSolver::solveSudoku(1, 1);
			//showSudoku(problem_sudoku);
			//if (checkSudoku(SudokuSolver::problem_sudoku))//检查是否符合数独要求，release模式下注释掉
			//	cout << "Wrong!" << endl;
			if (is_end && i == num_in_read_buff - 1)
				printSudoku(SudokuSolver::problem_sudoku, true);
			else
				printSudoku(SudokuSolver::problem_sudoku, false);
		}
	}
	for (int i = BUFF_SIZE; i >= 0; i--)
		freeSudoku(read_buff[i]);
	for (int i = 2; i >= 0; i--)
		freeSudoku(SudokuSolver::rule[i]);
	freeSudoku(SudokuSolver::covered);
}

